// 题目描述
// 410. 分割数组的最大值
// 困难
// 838
// 给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
// 设计一个算法使得这 m 个子数组各自和的最大值最小。
//   示例 1：
// 输入：nums = [7,2,5,10,8], m = 2
// 输出：18
// 解释：
// 一共有四种方法将 nums 分割为 2 个子数组。
// 其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
// 因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
// 示例 2：
// 输入：nums = [1,2,3,4,5], m = 2
// 输出：9
// 示例 3：
// 输入：nums = [1,4,4], m = 3
// 输出：4
//   提示：
// 1 <= nums.length <= 1000
// 0 <= nums[i] <= 106
// 1 <= m <= min(50, nums.length)
// 通过次数
// 70.8K
// 提交次数
// 120K
// 通过率
// 59.0%
// https://leetcode.cn/problems/split-array-largest-sum

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var splitArray = function (nums, k) {
  /**
   * 分组的个数（单调递减的 fx）
   * @param groupSumLimit 每个组数字和的上限
   * @returns {number}
   */
  function getGroupCnt(groupSumLimit) {
    let groupCnt = 0

    let memberSum = 0
    for (let i = 0; i < nums.length; i++) {
      memberSum += nums[i]
      if (memberSum === groupSumLimit) {
        ++groupCnt
        memberSum = 0
      } else if (memberSum > groupSumLimit) {
        ++groupCnt
        memberSum = nums[i]
      }
    }

    groupCnt += (memberSum > 0) ? 1 : 0

    return groupCnt
  }

  let [left, right] = nums.reduce(([l, r], cur) => {
    return [Math.min(l, cur), r + cur]
  }, [0, 0])
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2)
    const groupCnt = getGroupCnt(mid)
    if (groupCnt ===  k) {
      right = mid - 1
    } else if (groupCnt > k) {
      left = mid + 1
    } else if (groupCnt < k) {
      right = mid - 1
    }
  }

  return left
}

const nums = [1, 4, 4]
function getGroupCnt(groupSumLimit) {
  let groupCnt = 0

  let memberSum = 0
  for (let i = 0; i < nums.length; i++) {
    memberSum += nums[i]
    if (memberSum === groupSumLimit) {
      ++groupCnt
      memberSum = 0
    } else if (memberSum > groupSumLimit) {
      ++groupCnt
      memberSum = nums[i]
    }
  }

  groupCnt += (memberSum > 0) ? 1 : 0

  return groupCnt
}

console.log(
  getGroupCnt(4)
)
